/*
 * Copyright 2011-2012 by The Regents of the University of California Licensed
 * under the Apache License, Version 2.0 (the "License"); you may not use this
 * file except in compliance with the License. you may obtain a copy of the
 * License from
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package edu.ucsd.db.bassarisk.query.predicate;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.commons.lang3.StringUtils;

import edu.ucsd.db.bassarisk.query.binding.BindingSet;
import edu.ucsd.db.bassarisk.query.binding.Bindings.Binding;
import edu.ucsd.db.bassarisk.query.binding.Bindings.BindingUnion;
import edu.ucsd.db.bassarisk.query.binding.Bindings.PositionBinding;
import edu.ucsd.db.bassarisk.query.binding.Bindings.RunBinding;

public class PredicateGuardTable {
  private final BitSet[] columnMasks;
  private final int columns;
  private final List<Integer> decisionPoints;
  private final List<Integer> guardableBindings;
  private final int rows;
  private final String runClassName;
  private final short[] table;

  public PredicateGuardTable(final BindingSet bindings, final String runClassName) {
    this.runClassName = runClassName;
    this.guardableBindings = new ArrayList<Integer>();
    this.decisionPoints = new ArrayList<Integer>();
    // FIXME should we be looking at names here, or true run-class
    // relationships?
    for (Binding binding : bindings) {
      if (!binding.boundSequenceClass().getName().equals(runClassName)) {
        continue;
      }
      if (binding instanceof PositionBinding || binding instanceof RunBinding) {
        this.guardableBindings.add(binding.getId());
      } else if (binding instanceof BindingUnion) {
        // TODO if all binding's children are PositionSetBindings....
        // then add to guardable and remove children (and prevent later
        // additions)
        this.decisionPoints.add(binding.getId());
      }
    }
    this.columns = this.guardableBindings.size();
    this.rows = this.decisionPoints.size();
    this.table = new short[this.columns * this.rows];
    Arrays.fill(this.table, (short) -1);
    this.columnMasks = new BitSet[this.columns];
    for (int column = 0; column < this.columns; ++column) {
      this.columnMasks[column] = new BitSet(bindings.count());
      int bindingId = this.guardableBindings.get(column);
      while (bindingId >= 0) {
        Binding binding = bindings.getById(bindingId);
        if (binding.inUnion()) {
          int row = this.decisionPoints.indexOf(binding.getParent().getId());
          this.setGuard(column, row, binding.getId());
          this.columnMasks[column].set(binding.getId());
          bindingId = binding.getParent().getId();
        } else if (binding.inProduct()) {
          bindingId = binding.getParent().getId();
        } else {
          bindingId = -1;
        }
      }
    }
  }

  /**
   * Check to see if two guards are predicate compatible. Two guards are
   * compatible if they do not conflict in any disjunction decisions. Only
   * compatible columns may be compared by predicates.
   */
  public boolean areCompatible(final int guard1, final int guard2) {
    for (int i = 0; i < this.rows; i++) {
      int choice1 = this.getGuard(guard1, i);
      if (choice1 == -1) {
        continue;
      }
      int choice2 = this.getGuard(guard2, i);
      if (choice2 == -1) {
        continue;
      }
      if (choice1 != choice2) { return false; }
    }
    return true;
  }

  public int bindingAtColumn(final int columnIndex) {
    return this.guardableBindings.get(columnIndex);
  }

  /**
   * Finds all bindings between two specified bindings which are compatible with
   * both. Groups these bindings by their guards, and counts each group.
   */
  public Map<BitSet, Integer> countGuardedBindingsBetween(final int guard1,
                                                          final int guard2) {
    Map<BitSet, Integer> returnMap = new HashMap<BitSet, Integer>();
    int testGuard = guard1 + 1;
    BitSet currentGuard = this.columnMasks[testGuard];
    int currentGuardCount = 0;
    for (; testGuard < guard2; ++testGuard) {
      // If not compatible with either bookend, skip it.
      if (!this.areCompatible(guard1, testGuard)) {
        continue;
      }
      if (!this.areCompatible(testGuard, guard2)) {
        continue;
      }
      if (currentGuard.equals(this.columnMasks[testGuard])) {
        currentGuardCount++;
      } else {
        if (currentGuardCount > 0) {
          returnMap.put(currentGuard, currentGuardCount);
          currentGuardCount = 1;
          currentGuard = this.columnMasks[testGuard];
        }
      }
    }
    if (currentGuardCount > 0) {
      returnMap.put(currentGuard, currentGuardCount);
    }
    return returnMap;
  }

  public int getColumnNumber(final Binding setBinding) {
    int number = this.guardableBindings.indexOf(setBinding.getId());
    assert number >= 0;
    return number;
  }

  private short getGuard(final int guardableIndex, final int decisionIndex) {
    return this.table[this.tableIndex(guardableIndex, decisionIndex)];
  }

  public String getRunClassName() {
    return this.runClassName;
  }

  private boolean isGuarded(final int guardableIndex, final int decisionIndex) {
    return this.table[this.tableIndex(guardableIndex, decisionIndex)] >= 0;
  }

  public BitSet minimumGuard(final int bind1id, final int bind2id) {
    BitSet bind1guardCopy = (BitSet) this.columnMasks[bind1id].clone();
    bind1guardCopy.or(this.columnMasks[bind2id]);
    return bind1guardCopy;
  }

  private void setGuard(final int guardableIndex, final int decisionIndex,
                        final int guardId) {
    assert guardId < Short.MAX_VALUE;
    this.table[this.tableIndex(guardableIndex, decisionIndex)] = (short) guardId;
  }

  private int tableIndex(final int guardableIndex, final int decisionIndex) {
    // this defines a column major layout that is used to speed up some other
    // algorithms. (e.g. copying columns is fast)
    return decisionIndex + guardableIndex * this.rows;
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("\n").append("Guard Table for '").append(this.runClassName)
        .append("': \n");
    String format = "%4s |" + StringUtils.repeat(" %3s", this.columns);
    Object[] formatArgs = new Object[this.columns + 1];
    formatArgs[0] = "";
    for (int c = 0; c < this.columns; ++c) {
      formatArgs[c + 1] = this.guardableBindings.get(c);
    }
    sb.append(String.format(format, formatArgs)).append("\n");
    sb.append("-----|").append(StringUtils.repeat("----", this.columns))
        .append("\n");
    for (int r = 0; r < this.rows; ++r) {
      formatArgs[0] = this.decisionPoints.get(r);
      for (int c = 0; c < this.columns; ++c) {
        formatArgs[c + 1] = this.isGuarded(c, r) ? (int) this.getGuard(c, r) : "";
      }
      sb.append(String.format(format, formatArgs)).append("\n");
    }
    return sb.toString();
  }
}
